package com.wrial.kind.sort;
/*
 * @Author  Wrial
 * @Date Created in 8:51 2020/8/8
 * @Description
 *
 * 快速排序
 */

import java.util.Queue;

public class QuickSort {

    // 快排
    public int[] sortArray(int[] nums) {
        myQuickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void myQuickSort(int[] nums, int start, int end) {
        int pivot = nums[(start + end) / 2];
        int pl = start, pr = end;

        while (pl < pr) {
            while (nums[pl] < pivot) {
                pl++;
            }
            while (nums[pr] > pivot) {
                pr--;
            }
            if (pl > pr) break;  //此处break后去递归，条件不要粗心大意写错
            int temp = nums[pl];
            nums[pl] = nums[pr];
            nums[pr] = temp;
            if (nums[pl] == pivot) {
                pl++;
            }
            if (nums[pr] == pivot) {
                pr--;
            }
        }
        if (pr > start) myQuickSort(nums, start, pr);
        if (pl < end) myQuickSort(nums, pl, end);
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 3, 8, 9, 0, 1, -5, -55};
        new QuickSort().sortArray(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }

}
